package StruttureDati;

public class VisitaIterativa {
	//static int count=0;
	String res;//risultato da restituire
	SimpList<Env> p;//pila x gestire la ricorsione
	Env ec;//ambiente corrente
	VisitaIterativa(){res="";}
	public static String visita(SimpBtree<Integer> t){//simmetrica
		if(t.empty())return "";
		else return "<"+visita(t.left())+" "+ t.root()+" "+visita(t.right())+">";
	}  
	enum Label{entry1,entry2,entry3 }
	class Env{
		String res;//metodo di tipo funzione
		SimpBtree<Integer> t;//parametro formale
		Label entry;//etichetta di ritorno
		Env(SimpBtree<Integer> t){this.t=t;entry=Label.entry1;res="";}
		public String toString(){
			return "res="+res+",t="+t+" , entry="+entry;
		}
	}
    public String visitaIterativa(SimpBtree<Integer> t){
 //   	System.out.println("inizio visita iterativa");
    	p=SimpList.EMPTYLIST;// la pila viene inizializzata
    	ec=new Env(t);//l'albero viene inizializzato
    	boolean returnPoint=false;//serve a saltare il test di pila non vuota
    	while(true){
   // 		count++;
   // 		System.out.println("*********count="+count+" albero="+ec.t);
    	switch(ec.entry){
    	case entry1://start
    		if(ec.t.empty()){res="";returnPoint=true;break;}//vado a pila vuota
    		else {ec.res=res+"<";ec.entry=Label.entry2;
    		    System.out.println("sottoalbero sinistro ec-push: "+ec);
    		     p=new SimpList<Env>(ec,p);// push xche' vado a chiamare visita(t.left());
    		     ec=new Env(ec.t.left());
    //		     System.out.println("sottoalbero sinistro ec-nuovo: "+ec);
    		     returnPoint=false;break;}
    	case entry2://dopo la visita del sooalbero sinistro
    		       ec.res=ec.res+res+" "+ec.t.root()+" ";
    		       ec.entry=Label.entry3;
    	//	       System.out.println("sottoalbero destro ec: "+ec);
    		       p=new SimpList<Env>(ec,p);// push xche' vado a chiamare visita(t.right());
    		       ec=new Env(ec.t.right());returnPoint=false;break;
    	case entry3://dopo la visita del sottoalbero destro
   // 		   System.out.println("entry3 res="+res+",ec.res="+ec.res);
    	       res=ec.res+" "+res+">";
    	 //      System.out.println("entry3 res="+res);
    	       returnPoint=true;break;
    		     }
   	//salto alla pila non vuota se non ho fatto push ovvero returnPoint=true
    		if(!p.empty()&&returnPoint){ec=p.head();
    	//		System.out.println("pila non vuota ec="+ec);
    			p=p.tail();}
    		else if(returnPoint){//System.out.println("pila vuota res="+res);
    		                     return res;}
    		}//fine del while
 //   	    System.out.println("fine errata");return res;
    	}
    public static void main(String args[]){
    	SimpBtree<Integer> t=new SimpBtree<Integer>(15,SimpBtree.EMPTYBTREE,SimpBtree.EMPTYBTREE);
    	t=new SimpBtree<Integer>(25,t,SimpBtree.EMPTYBTREE);
    	System.out.println(visita(t));
    	VisitaIterativa o=new VisitaIterativa();
    	System.out.println("stampa iterativa="+o.visitaIterativa(t));
    	
    }
    }
